import common.TreeNode;

/**
 * 543. Diameter of binary tree 二叉树的直径
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 */
class DiameterOfBinaryTree {
    private int ans;

    /**
     * 方法：DFS后序遍历，计算每个节点的左右子树最大深度，更新最大直径
     * 
     * Args:
     *   root: 二叉树根节点
     * 
     * Returns:
     *   二叉树的直径(最长路径的长度)
     * 
     * Time: O(N), N为节点数,每个节点遍历一次
     * 
     * Space: O(H), H为树高,递归栈空间
     */
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node){
        if(node == null){
            return -1;
        }
        int l_len = dfs(node.left) + 1;// 左子树最大链长+1
        int r_len = dfs(node.right) + 1;// 右子树最大链长+1
        ans = Math.max(ans, l_len + r_len);// 两条链拼成路径
        return Math.max(l_len, r_len);// 当前子树最大链长
    }
}